/*?
? LRU是Least Recently Used的缩写，译为最近最少使用。它的理论基础为 “最近使用的数据会在未来一段时期内仍然被使用，已经很久没有使用的数据大概率在未来很长一段时间仍然不会被使用”
? 由于该思想非常契合业务场景 ，并且可以解决很多实际开发中的问题，所以我们经常通过LRU的思想来作缓存，一般也将其称为LRU缓存机制。

? 思考：有没有考虑过LRU算法实现中为什么使用map，它的好处是什么？对于LRU算法，是get使用频率更高还是put使用频率更高？为什么？LRU算法的使用场景？
?    一：使用map，它的好处是什么?:
?    1. 时间复杂度：使用 map 可以从 O(n) 降到 O(1)，因为 map 在查找是否存在某个键值对的时候，可以通过对键进行哈希运算，快速定位到哈希表中的位置，从而实现快速查找。
?    2. 空间复杂度：使用 map 可以节省空间，因为 LRU 算法需要一个能够快速插入和删除元素的容器，而 map 内部采用红黑树实现，可以高效地完成插入、删除等操作。
?    3. 易于实现：使用 map 可以简化 LRU 算法的实现，因为 map 自带了许多功能，例如插入、删除、查找等，可以减少代码量和工作量。
?    二：对于LRU算法，是get使用频率更高还是put使用频率更高？为什么？:
?    在 LRU（最近最少使用）算法中，get 操作可能更频繁使用，因为它用于获取缓存中存储的元素，如果缓存中存在需要的数据，那么就可以直接返回，从而避免了对底层存储介质的访问，因此会更加快速和高效。
?    相比之下，put 操作可能较少使用，因为它用于将新的数据存储到缓存中，如果缓存已满，则需要先淘汰掉最近最少使用的元素，从而为新的数据腾出空间，这个操作需要额外的时间和计算资源，因此相对来说 put 操作的使用频率可能会稍微低一些。
?    三：LRU算法的使用场景？
?    1. Web 缓存：用于缓存最近的 Web 页面，从而避免重复的网络请求和数据传输，提高 Web 页面的加载速度。
?    2. 数据库引擎：用于缓存经常访问的数据页，从而减少磁盘 IO 操作，提高数据库系统的响应能力和性能。
?    3. 操作系统页缓存：用于缓存最近访问的文件页，提高操作系统的磁盘 IO 性能。
?    4. 图像处理：用于缓存最近使用的图像数据，提高图像处理的性能和响应速度。
?    5. 电子商务：用于缓存最近访问的商品数据，从而加快网站的加载速度和响应时间。
?    6. Vue keep-alive中所使用的结构
?    总之，任何需要对访问模式进行优化的场景都可能会使用到 LRU 算法，从而提高数据访问的效率和性能。
?    四:使用map来实现LRU算法在delete时的时间复杂度为O(n),这是可以优化的点
?    使用双向链表 + map实现LRU缓存结构
整理一下使用Map和链表来实现LRU缓存的思路：
1.使用Map作为Cache缓存区，Map的key为传入的key，value为双向链表中的节点。
2.双向链表中的节点包含四个属性：

key (节点的键)
value（节点的值）
next（指向下一个节点）
prev（指向前一个节点）
3.当执行get操作时，需要先判断Map中是否存在对应的key:

如果不存在，直接return -1；
如果存在，就要先在Map和链表里删除当前节点，然后把当前节点添加至头节点后边&Map的尾部（Map里越往后优先级越高），然后返回节点的value值；
4.当执行put操作时，需要先判断Map中是否存在要put的key：

如果已存在该key，为了保证优先级，需要在Map和链表中都先删除当前节点，然后添加当前节点至链表头节点之后&Map的尾部；
如果不存在该key，则需要根据Map的size和容量capacity的大小关系分别处理：
如果Map的size大于等于capacity，则需要删除链表除尾结点的最后一个节点&Map的第一个元素，然后添加新节点至头节点之后&Map的尾部；
如果Map的size小于capacity，直接添加新节点至头节点之后&Map的尾部；
?    https://github.com/Sunny-117/js-challenges/issues/272
?
*/


//? 1.传统map实现
class LRUCache6 {
    constructor(capacity) {
        //? 容量
        this.capacity = capacity;
        //? map存储
        this.cache = new Map();
    }
    get(key) {
        if (!this.cache.has(key)) {
            return -1
        }
        const val = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, val)
        return val
    }
    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        }
        //? 因为要set 所以条件是>=
        if (this.cache.size >= this.capacity) {
            let key = this.cache.keys().next().value;
            //? 获取第一个key的值(map.keys()返回的是一个迭代器对象,其内部有iteration index, 故可以使用next()) 删掉最不常用的
            //? map数据结构能够保持插入顺序，而obj不能
            this.cache.delete(key);
        }
        this.cache.set(key, value);
    }
    toString() {
        console.log('capacity', this.capacity);
        console.table(this.cache);
    }
}


const lruCache6 = new LRUCache6(2);
lruCache6.put(1, 'first');
lruCache6.put(2, 'second');
lruCache6.get(1);
lruCache6.toString()
lruCache6.put(3, 'third');
lruCache6.toString();
//? 2.双向链表 + map
//? 定义双向链表
//? 双向 所以有next也有prev
class Node {
    constructor(key = '', value = '') {
        this.key = key
        this.value = value
        this.next = null
        this.prev = null
    }
}
class LinkList {
    constructor() {
        let head = new Node('head','head')
        let tail = new Node('tail','tail')
        head.next = tail
        tail.prev = head
        this.head = head
        this.tail = tail
    }
    //? 头插
    append(node) {
        node.next = this.head.next
        node.prev = this.head
        this.head.next.prev = node
        this.head.next = node
    }
    //? 删除最后一个节点(非tail)
    pop() {
        let node = this.tail.prev;
        node.prev.next = this.tail
        this.tail.prev = node.prev
        return node
    }
    //? 删除指定节点
    delete(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
    }
}
class LRU {
    constructor(capacity) {
        this.capacity = capacity;
        this.kvMap = new Map();
        this.linkList = new LinkList();
    }
    put(key,value) {
        if (this.kvMap.has(key)) {
            let node = this.kvMap.get(key)
            //? 直接map修改值而不删除
            node.value = value
            this.linkList.delete(node)
            this.linkList.append(node)
        }
        else {
            let node = new Node(key,value)
            if (this.capacity === this.kvMap.size) {
                let nodeP = this.linkList.pop()
                this.kvMap.delete(nodeP)
            }
            //? Map的key为传入的key，value为双向链表中的节点
            this.kvMap.set(key, node);
            this.linkList.append(node);
        }
    }
    get(key) {
        //? 没有 则-1
        if (!this.kvMap.has(key)) {
            return -1;
        }
        //? 有 也是先删后加(使用Map作为Cache缓存区，Map的key为传入的key，value为双向链表中的节点。)
        let node = this.kvMap.get(key);
        this.linkList.delete(node);
        this.linkList.append(node);
        return node.value;
    }
}
